#include <iostream>
#include <algorithm>

const int n = 10;                         // 物品数量
int w[] = {2, 3, 8, 9, 4, 7, 4, 3, 8, 9}; // 重量
int v[] = {4, 8, 3, 4, 9, 7, 3, 2, 9, 9}; // 价值

const int C = 25; // 最大重量

int x[n]; // 01向量

int CurWeight = 0; //当前放入背包的物品总重量
int CurValue = 0;  //当前放入背包的物品总价值

void backtrack(int t, int *bestValue, int **bestX)
{
    // 叶子节点输出
    if (t == n - 1)
    {
        if (CurValue > *bestValue)
        {
            //如果找到了一个更优的解
            //保存更优的值和解
            *bestValue = CurValue;
            for (int i = 0; i < n; i++)
            {
                (*bestX)[i] = x[i];
            }
        }
        return;
    }

    // 不装的情况, i=0
    x[t] = 0;
    backtrack(t + 1, bestValue, bestX);

    // 装的情况, i=1
    x[t] = 1;
    // 约束条件：放得下
    if (CurWeight + w[t] <= C)
    {
        CurWeight += w[t];
        CurValue += v[t];
        backtrack(t + 1, bestValue, bestX);
        CurWeight -= w[t];
        CurValue -= v[t];
    }
}

int main(int argc, char *argv[])
{
    int bestValue = 0;
    int *bestX = new int[n];

    backtrack(0, &bestValue, &bestX);

    printf("最优值：%d\n", bestValue);

    printf("最优解: ");
    for (int i = 0; i < n; i++)
    {
        printf("%-3d", bestX[i]);
    }
    printf("\n");
    delete[] (bestX);
    return 0;
}